public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        System.out.println(test.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
    }

    public int maxArea1(int[] height) {
        /**
         * 盛水最多的容器
         * 解法1：暴力解法
         * 结果：超时，O（n²）的时间复杂度太高
         * */
        int n = height.length;
        int maxArea = 0;
        for(int i = 0; i < n - 1; i++) {
            for(int j = i + 1; j < n; j++) {
                int tempArea = Math.min(height[i], height[j]) * (j-i);
                if(maxArea < tempArea) {
                    maxArea = tempArea;
                }
            }
        }
        return maxArea;
    }

    public int maxArea(int[] height) {
        /**
         * 盛水最多的容器
         * 解法2：双指针解法
         * 算法思想：
         *  更新较小的边，因为更新时宽度在不断减少，因此若是遍历到的边都小于等于原边，则面积必定比原来的小，故可以while循环进行更新
         *  直到遍历到的边比原边大，此时再退出循环，重进循环时会更新面积
         * 结果：通过
         * */
        // 1 预处理
        int n = height.length;
        int left = 0;
        int right = n - 1;
        // -计算初始面积
        int maxArea = 0;
        // 2 双指针找到最大面积
        while(left < right) {
            // -更新最大面积区域
            int curArea = Math.min(height[left], height[right]) * (right-left);
            if(maxArea < curArea) {
                maxArea = curArea;
            }
            if(height[left] > height[right]) {
                // -l>r
                int temp = height[right];
                while(left < right && height[right] <= temp) {
                    right --;
                }
            } else {
                // -l<=r
                int temp = height[left];
                while(left < right && height[left] <= temp) {
                    left ++;
                }
            }
        }
        // 3 返回值
        return maxArea;
    }

}
